import pprint as pp
class Solution:
	# @param {string} s
	# @return {string}
	def longestPalindrome(self, s):
		''' Manacher Algorithm '''
		if len(s) < 2:
			return s
		ss = [None] + list('#'.join(list(s))) + [None]
		rad = [0 for c in ss]
		rad[0] = rad[-1] = 0
		i = 1
		while i < len(ss)-1:
			# print i
			if rad[i] == 0:
				j = 1
				while i-j > 0 and ss[i-j] == ss[i+j]:
					j += 1
				rad[i] = j-1
			for k in range(1, rad[i]+1):
				if rad[i] - k != rad[i-k]:
					rad[i+k] = min(rad[i-k], rad[i]-k)
				else:
					mid = i + k
					rad[mid] = rad[i-k]
					j = rad[mid] + 1
					while mid - j > 0 and ss[mid-j] == ss[mid+j]:
						j += 1
					rad[mid] = j-1
			#print rad
			if rad[i] != 0:
				i += rad[i]
			else:
				i += 1
		# generate answer
		ind = (0, 0)
		for x in range(1, len(ss)-1):
			if (rad[x] > ind[0]) or (rad[x] == ind[0] and ss[x] == '#'):
				ind = (rad[x], x)

		return "".join("".join(ss[ind[1]-ind[0]:ind[1]+ind[0]+1]).split('#'))

		

if __name__ == '__main__':
	print Solution().longestPalindrome('fffffffffffffffffffffff')

